package Top101;

import java.util.*;
import java.util.Arrays;

public class Test_9_25 {

    //BM89 合并区间
    public void merge(int A[], int m, int B[], int n) {
        if(n == 0) return;

        int k = m + n - 1;
        m--;
        n--;
        while(m >= 0 && n >= 0) {
            if(A[m] > B[n]) {
                A[k--] = A[m--];
            } else {
                A[k--] = B[n--];
            }
        }
        while(m >= 0) {
            A[k--] = A[m--];
        }
        while(n >= 0) {
            A[k--] = B[n--];
        }
    }


    //斐波那契数列
    public int Fibonacci (int n) {
        if(n == 1 || n == 2) return 1;

        int  numb1 = 1;
        int numb2 = 1;
        int ret = 0;
        for(int i = n - 2; i > 0; i--){
            ret = numb1 + numb2;
            numb1 = numb2;
            numb2 = ret;
        }
        return ret;
    }



    //三数之和
    public ArrayList<ArrayList<Integer>> threeSum (int[] num) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        if(num.length == 0) return ret;

        Arrays.sort(num);
        for(int i = 0; i < num.length - 2; i++) {
            int sum = 0 - num[i];
            int left = i + 1;
            int right = num.length - 1;
            while(left < right) {
                if(num[left] + num[right] == sum) {
                    ArrayList<Integer> tmp = new ArrayList<>();
                    tmp.add(num[i]);
                    tmp.add(num[left]);
                    tmp.add(num[right]);
                    if(!ret.contains(tmp)) ret.add(tmp);
                    left++;
                    right--;
                } else if(num[left] + num[right] > sum) {
                    right--;
                } else {
                    left++;
                }
            }
        }

        return ret;
    }



    //有效括号序列
    public boolean isValid (String s) {
        if(s.length() == 0) return true;
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            } else {
                if(stack.empty()) return false;
                char top = stack.peek();
                if(top == '(' && ch == ')' || top == '[' && ch == ']' || top == '{' && ch == '}') {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }

        if(stack.empty()) return true;
        return false;
    }

}
